Digital systems transmit quantized data. In a binary system, the quantized data is represented by either a zero or a one. During the transmission of digital signals, noise from a variety of sources corrupt the transmitted signal so that what is received is not necessarily the same signal that was transmitted. To compensate for noise and to enhance accurate detection, error-correction techniques are commonly employed.
One method for enhancing the accuracy in detecting a transmitted signal is to convolutionally encode the signal prior to transmission. Instead of transmitting the source signal, the encoded signal is transmitted. The convolutional encoder adds redundancy to the source signal by generating a predetermined number of bits according to a binary logic calculation for each source signal bit, or set of bits. The number of bits generated by the encoder is greater than the number of bits input to the encoder from the source signal. Consequently, information relating to the identity of each source signal bit is transmitted in more than one bit. Thus, the receiver has more opportunity to accurately detect the source signal bit than would be available if only the source signal bit was transmitted. The use of convolutional encoders is more fully described in Peyton Z. Peebles, Jr., Digital Communication Systems, pp.87-102 (Prentice Hall 1987) hereby incorporated by reference as if fully set forth herein.
Error correction techniques involve using the Viterbi algorithm in a receiver, as a Viterbi decoder. The premise of the Viterbi decoder is that for each signal received at a time instant, there exists a finite number of states to represent the source signal. As each signal is received, the Viterbi decoder traces a transition from each of a finite number of possible present states reflecting the signal received one time instant earlier, to each of a finite number of possible next states. Where the source signal was first convolutionally encoded prior to transmission, the Viterbi decoder uses the encoder scheme to generate a possible representation of the received signal, for each transition from present state to next state. Generally, a received signal is presented to the decoder as a symbol which comprises one or more bits. The size of the source signal corresponding to a received symbol set largely depends on the code rate. Thus for a rate one half encoder, where one source signal bit is transmitted as two bits, a symbol set comprises two bits and the corresponding source signal comprises one bit.
Thus, a set of transmitted digital signals are represented by one or more possible sequences of state transitions. Each transition is referred to as a branch, and a sequence of branches form a path. Since each branch indicates a possible representation of a transmitted digital signal, an error value equal to the difference between the Viterbi generated signal of a particular branch and the signal actually received at that corresponding time instant, can be computed and evaluated. This error is referred to as a branch metric. The branch metric can be used to determine whether a particular state at one time instant accurately represents a corresponding source signal. Since the accuracy of each state depends on the sequence of states at earlier time instants leading to that state, each state can be associated with an error, i.e., an accumulated cost value, which is equal to the sum of the sequence of branch metrics leading to that state. Likewise, after all the digital signals are received and the path is complete, an accumulated cost can be associated with each path. The path indicating the smallest error is selected to represent the sequence of source signal bits.
The Viterbi decoder is generally implemented in a receiver twice. A first Viterbi decoder is used to determine the transmitted bits from the received signal. This first Viterbi decoder is generally referred to as an equalizer. A second Viterbi decoder is used to determine the source signal from the transmitted bits based on the encoder scheme. The performance of the second Viterbi decoder is enhanced where the first Viterbi decoder is a soft decision decoder which provides a soft-symbol output. While a Viterbi decoder described above translates each received symbol set as a 0 or a 1 source bit, i.e. hard bits, a soft decision Viterbi decoder obtains an indication of the reliability of the hard bit, as well. For instance, a received signal having a value of 0.9 is likely to be quantized into a hard 1. Indeed, it is very likely that 0.9 was transmitted as a 1. Likewise, a value of 0.1 is likely to be quantized as a hard 0. Again, the probability is high that this quantization is correct. However, when the received signal is 0.5, the level of confidence that the signal was transmitted as a 0 or a 1 is very low.
One method for obtaining soft-symbol decision is described in U.S. Pat. No. 5,471,500 entitled "Soft-Symbol Decoding," which issued to Blaker on Nov. 28, 1995 and is commonly assigned with the present application, the disclosure of which is hereby incorporated by reference as if fully set forth herein. This method involves concatenating the decoded hard bit associated with a particular branch, with its branch metric. This combination is referred to as a soft symbol decoded signal. While the hard bit simply indicates the best choice from the available alternatives, the branch metric or the accumulated cost difference indicates the degree of error between the selected hard bit and the received digital signal. The soft symbol therefore provides a measure of the reliability of the selected hard bit.
Two common metric schemes for calculating branch metrics are "Manhattan" and "Hamming." In the Manhattan metric scheme, digital signals are usually represented in an unsigned binary number system. Thus, logical zero represented with eight digits in unsigned binary, is indicated by 0000 0000. Likewise, logical one is shown by 1111 1111. The branch metric of a given branch is calculated by taking the absolute value difference between each received digital signal and the corresponding digital signal computed internally by the Viterbi decoder and indicated by the branch. For the Manhattan branch metric scheme, the smallest error is indicated by an extremum branch metric, typically the smallest. Accordingly, a Viterbi decoder designed for a Manhattan branch metric will select as the most likely path, the path associated with the least cost relative to all possible paths.
In the Hamming branch metric scheme, digital signals are usually represented in a signed complement number system. In signed complement, the sign of the number is indicated by the most significant digit. Usually, a 0 indicates a positive value and a 1 indicates a negative value, although, the reverse is valid as well. The remaining digits, properly complemented, indicate the magnitude. The magnitude of a number with a leading 0 is the same as if the number was in unsigned binary form. For example, 0110 equals 6 in unsigned binary and +6 in a signed complement form where 0 indicates a positive value. A number having the same magnitude but the opposite sign of a second number, is represented by the complement of the second number. For example, -6 is represented by the complement of 0110, +6. One signed complement system is known as one's complement which involves changing all 0's to 1's and 1's to 0's. Thus -6 in one's complement form is shown as 1001. Another signed complement system is known as two's complement, which simply requires the addition of a 1 to the one's complement. Thus, -6 in two's complement form is shown as 1010. Hamming metrics often involve two's complement. A description of complements and mathematical operations with numbers in a complement number system can be found in M. Morris Mano, Computer Engineering: Hardware Design, pp. 11-17 (Prentice Hall 1988), hereby incorporated by reference as if fully set forth herein.
One implementation of the Hamming metric scheme referred to as Hamming 1, maps logical one to a positive one and logical zero to a negative one, so that logical one represented with eight digits in two's complement will be shown by 0111 1111 and logical zero will be shown by a 1000 0000. Alternatively, the Hamming 2 branch metric scheme maps logical one to a negative one and logical zero to a positive one, such that logical one will be shown by 1000 0000 and logical zero will be shown by 0111 1111. As described, the two Hamming metric schemes are the one's complement of each other.
In contrast to a Manhattan metric scheme based decoder, a Viterbi decoder designed for a Hamming metric scheme will select the path associated with the highest positive or negative cost relative to all possible paths. The reason for this stems from the calculation of the Hamming branch metric. Instead of calculating the absolute value difference between each received digital signal and the corresponding digital signal computed internally by the Viterbi decoder, as is done for Manhattan metrics, Hamming takes into consideration the sign of the magnitude of the signal. One familiar with mathematical operations of numbers in a signed complement system, will readily recognize that the smallest error in Hamming, is indicated by the largest branch metric.
As stated above, a Viterbi decoder designed for a Manhattan metric scheme will typically select the path associated with the least cost. However, the path associated with the least cost, represents the best path only when the signal to be decoded is in unsigned binary. In this system, the closer in value the received signal is to 0, the more likely the signal was transmitted as a 0. Similarly, the closer in value the received signal is to 1 the more likely the signal was transmitted as a 1. In either case, the difference in value between the received signal and the most likely transmitted signal bit is less than the difference in value between the received signal and any other possible representation of the transmitted signal. Thus, a Manhattan metric scheme based Viterbi decoder is only compatible with an input signal in unsigned binary. Likewise a soft decision Viterbi decoder results in a soft symbol decoded output in unsigned binary.
In contrast, a Viterbi decoder designed for a Hamming metric scheme typically selects the path associated with the greatest positive or negative cost. To properly select the most likely path, the signal received by the Viterbi decoder must be in a signed complement system, preferably two's complement.
When a digital signal is represented in two's complement and confined to a certain number of digits, for example eight, logical 1 will be represented by a range of discrete values, each value indicative of a different degree of confidence. Logical 0 is also represented by a range of discrete values indicative of different degrees of confidence. A particular degree of confidence for logical 1 is indicated by the two's complement of the value indicating the same degree of confidence for logical 0.
For example, an eight-digit number in Hamming 2, where logical 1 is mapped to positive values, i.e., leading 0's and logical 0 mapped to negative values, i.e., leading 1's, the lowest confidence 1 and 0 are indicated by 0000 0000 and 1111 1111, respectively. The highest confidence 1 and 0 are indicated by 0111 1111 and 1000 0000, respectively. For Hamming 1 where logical 1 is mapped to negative values and logical 0 is mapped to positive values, the lowest confidence 1 and 0 are indicated by 1111 1111 and 0000 0000, respectively.
Although an astute reader will recognize that the numbers representing the extreme confidence levels of logical 1 and 0 are actually one's complement of each other, intermediate levels of confidence for logical 1 and 0 are indicated by two's complement.
The problem arises in signal processing applications where some aspects of an application, such as an Equalizer in a decoder, employ either a Manhattan or Hamming branch metric scheme, while other aspects of the same application, such as the second stage Viterbi decoder, are configured for the other branch metric scheme.
More specifically, some applications are designed to represent signals in two's complement. Consequently, any component, such as a Viterbi decoder, that must calculate or recognize a metric, must do so in Hamming. The same is true for an application designed to represent signals in an unsigned binary system. Traditionally, these two systems require components specifically designed for their number system. In other words, Hamming for the first system and Manhattan for the second. This is inefficient where both components are required for the same task. Moreover, it may be the case that the component designed for Manhattan performs better than the same component designed for Hamming or vice versa. It would then be advantageous to be able to use the Manhattan component even with an application that traditionally requires a Hamming component.